package com.lfd.datastructure.sort;

import java.util.Arrays;

/**
 * @项目名： spring-emq
 * @包名： com.lfd.datastructure.sort
 * @文件名: BubbleSort
 * @创建者: liufudong@szyh-smart.com
 * @创建时间: 2024/10/27 19:58
 * @描述：冒泡排序是一种简单的排序算法，其基本原理是通过重复遍历待排序的数列，比较相邻的元素并交换它们的顺序 ，从而将最大的元素“冒泡”到数列的末尾
 * 。这个过程会持续进行，直到整个数列有序为止。
 * 冒泡排序的具体步骤：
 * 比较相邻元素：从数列的第一个元素开始，比较相邻的两个元素。如果第一个元素大于第二个元素，则交换它们的位置。
 * 向后移动：继续比较下一个相邻的元素，重复步骤1，直到比较到数列的末尾。此时，最大的元素会被移动到最后的位置。
 * 重复操作：忽略已排序的最后一个元素，重复上述过程，直到没有需要交换的元素为止。
 * 冒泡排序的时间复杂度：
 * 最佳情况：O(n)（当数列已经有序时，只需一次遍历）
 * 最坏情况：O(n^2)（当数列完全逆序时，需要进行 n-1 次比较和交换）
 * 平均情况：O(n^2)
 * 示例代码（Java）：
 */
public class BubbleSort {
    public static void main(String[] args) {
        int[] ints = bubbleSort(new int[]{1, 3, 5, 7, 2, 4, 6,20, 8});
        System.out.println("BubbleSort" + Arrays.toString(ints));
        int[] ints2 = bubbleSort(new int[]{1, 2, 3, 4, 5, 6, 7, 8});
        System.out.println("BubbleSort" + Arrays.toString(ints2));
    }

    public static int[] bubbleSort(int[] arr) {
        boolean swapped = false;

        for (int i = 0; i < arr.length - 1; i++) {
            swapped = false;
            for (int j = 0; j < arr.length - 1 - i; j++) {
                if (arr[j] > arr[j + 1]) {
                    int temp = arr[j];
                    arr[j] = arr[j + 1];
                    arr[j + 1] = temp;
                }
                swapped = true;
            }// 如果没有发生交换，说明数组已经有序
            if (!swapped) {
                break;
            }
        }
        return arr;
    }
}
